DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2019.26

Space Lower Bounds for the Signal Detection Problem

Authors: Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract

Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n+1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader’s preceding step; otherwise it must return false. Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m >= 2^n. But a proof of this conjecture remains elusive. We prove a lower bound of m >= n^2, as well as a tight lower bound of m >= 2^n for two restricted versions of the problem, where the processes are oblivious or where the signaller always resets the blackboard to the same fixed value. We also consider a one-shot version of the problem, where each reader takes at most two steps. In this case, we prove that it is necessary and sufficient that the blackboard can store m=n+1 values.

Cite as

Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu. Space Lower Bounds for the Signal Detection Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ellen_et_al:LIPIcs.STACS.2019.26,
  author =	{Ellen, Faith and Gelashvili, Rati and Woelfel, Philipp and Zhu, Leqi},
  title =	{{Space Lower Bounds for the Signal Detection Problem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.26},
  URN =		{urn:nbn:de:0030-drops-102654},
  doi =		{10.4230/LIPIcs.STACS.2019.26},
  annote =	{Keywords: Signal detection, ABA problem, space complexity, lower bound}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.17

Atomic Snapshots from Small Registers

Authors: Leqi Zhu and Faith Ellen

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract

Existing n-process implementations of atomic snapshots from registers use large registers. We consider the problem of implementing an m-component snapshot from small, Theta(log(n))-bit registers. A natural solution is to consider simulating the large registers. Doing so straightforwardly can significantly increase the step complexity. We introduce the notion of an interruptible read and show how it can reduce the step complexity of simulating the large registers in the snapshot of Afek et al. In particular, we show how to modify a recent large register simulation to support interruptible reads. Using this modified simulation, the step complexity of UPDATE and SCAN changes from Theta(n*m) to Theta(n*m+m*w), instead of Theta(n*m*w), if each component of the snapshot consists of Theta(w*log(n)) bits. We also show how to modify a limited-use snapshot to use small registers when the number of UPDATE operations is in n^{O(1)}. In this case, we change the step complexity of UPDATE from Theta((log(n))^3) to O(w + (log(n))^2*log(m)) and the step complexity of SCAN from Theta(log(n)) to O(m*w + log(n)).

Cite as

Leqi Zhu and Faith Ellen. Atomic Snapshots from Small Registers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{zhu_et_al:LIPIcs.OPODIS.2015.17,
  author =	{Zhu, Leqi and Ellen, Faith},
  title =	{{Atomic Snapshots from Small Registers}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.17},
  URN =		{urn:nbn:de:0030-drops-66084},
  doi =		{10.4230/LIPIcs.OPODIS.2015.17},
  annote =	{Keywords: atomic snapshot, limited-use snapshot, small registers, simulation}
}

Search Results

Documents authored by Zhu, Leqi

Space Lower Bounds for the Signal Detection Problem

Abstract

Cite as

Atomic Snapshots from Small Registers

Abstract

Cite as

Thanks for your feedback!

Could not send message